package nowcoder;

/**
 * @author wangxi created on 2021/5/9 18:17
 * @version v1.0
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
 */
public class ReConstructBinaryTree {

  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }


    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre == null || pre.length <= 0 || in == null || in.length <= 0) {
            return null;
        }
        int rootVal = pre[0];
        TreeNode root = new TreeNode(rootVal);
        int i = 0;
        for ( ; i < in.length; i++) {
            if (in[i] == rootVal) {
                break;
            }
        }
        if (i <= 0) {
            // 没有左子树
            root.left = null;
        } else {
            int[] preO = new int[i];
            int[] inO = new int[i];
            for (int j = 0; j < preO.length; j++) {
                preO[j] = pre[j + 1];
                inO[j] = in[j];
            }
            root.left = reConstructBinaryTree(preO, inO);
        }
        if (i >= in.length - 1) {
            root.right = null;
        } else {
            int[] preO = new int[pre.length - i - 1];
            int[] inO = new int[preO.length];
            for (int j = 0; j < preO.length; j++) {
                // 右子树的 前序与中序的数组获取方式是一致的。因为都是左子树+root+1 为起点
                // 注意：preO = pre[pre.length - i + j] 这样写法无法通过
                preO[j] = pre[i + j + 1];
                inO[j] = in[i + j + 1];
            }
            root.right = reConstructBinaryTree(preO, inO);
        }
        return root;
    }
}
